package com.example.tencentTrain;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？
 * 请你找出所有和为 0 且不重复的三元组。
 * 注意：答案中不可以包含重复的三元组。
 * <p>
 * 示例 1：
 * 输入：nums = [-1,0,1,2,-1,-4]
 * 输出：[[-1,-1,2],[-1,0,1]]
 * <p>
 * 示例 2：
 * 输入：nums = []
 * 输出：[]
 * <p>
 * 示例 3：
 * 输入：nums = [0]
 * 输出：[]
 */
public class Leetcode15_ThreeSum {
    public static void main(String[] args) {
        int[] nums = {-1, 0, 1, 2, -1, -4};
        System.out.println(new Solution().threeSum(nums));
    }

    static class Solution {
        /**
         * 解法二:双指针
         * 对数组进行排序后可以发现，当固定了前两重循环枚举到的元素 a 和 b，那么只有唯一的 c 满足 a+b+c=0。
         * 当第二重循环往后枚举一个元素 b' 时，由于 b' > b，那么满足 a+b'+c'=0的 c'一定有 c' < c
         * 即 c'在数组中一定出现在 c 的左侧。也就是说，我们可以从小到大枚举 b，同时从大到小枚举 c
         *
         * @param nums
         * @return
         */
        private List<List<Integer>> threeSum2(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            Arrays.sort(nums);
            if (nums == null || nums.length < 3 || nums[0] >= 0) return res;


            for (int first = 0; first < nums.length; ++first) {// 枚举 a
                // 需要和上一次枚举的数不相同
                if (first > 0 && nums[first] == nums[first - 1]) {
                    continue;
                }

                int third = nums.length - 1; // c 对应的指针初始为指向数组的最右端

                for (int second = first + 1; second < nums.length; ++second) {// 枚举 b
                    // 需要和上一次枚举的数不相同
                    if (second > first + 1 && nums[second] == nums[second - 1]) {
                        continue;
                    }

                    while (second < third // 保证 b 的指针在 c 的指针的左侧
                            && nums[first] + nums[second] + nums[third] > 0) {
                        --third;
                    }
                    // 如果指针重合，随着 b 后续的增加就不会有满足 a+b+c=0 并且 b<c 的 c 了，可以退出循环
                    if (second == third) {
                        break;
                    }

                    if (nums[first] + nums[second] + nums[third] == 0) {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[first]);
                        list.add(nums[second]);
                        list.add(nums[third]);
                        res.add(list);
                    }
                }
            }

            return res;
        }

        /**
         * 先排序然后三重循环遍历(超时)
         * 要保证三重循环三个数nums[i] <= nums[j] <= nums[k]
         * 同时，对于每一重循环而言，相邻两次枚举的元素不能相同，否则也会造成重复
         *
         * @param nums
         * @return
         */
        private List<List<Integer>> threeSum1(int[] nums) {
            List<List<Integer>> res = new ArrayList<>();
            if (nums == null || nums.length < 3) return res;
            Arrays.sort(nums);
            for (int i = 0; i < nums.length; i++) {
                if (i == 0 || nums[i] != nums[i - 1]) {
                    for (int j = i + 1; j < nums.length; j++) {
                        if (j == i + 1 || nums[j] != nums[j - 1]) {
                            for (int k = j + 1; k < nums.length; k++) {
                                if (k == j + 1 || nums[k] != nums[k - 1]) {
                                    int sum = nums[i] + nums[j] + nums[k];
                                    if (sum == 0) {
                                        List<Integer> list = new ArrayList<>();
                                        list.add(nums[i]);
                                        list.add(nums[j]);
                                        list.add(nums[k]);
                                        res.add(list);
                                    }
                                }
                            }
                        }
                    }
                }
            }

            // 不用去除重复的写法
//            for (int i = 0; i < nums.length; i++) {
//                for (int j = i + 1; j < nums.length; j++) {
//                    for (int k = j + 1; k < nums.length; k++) {
//                        if ((nums[i] + nums[j] + nums[k]) == 0) {
//                            List<Integer> list = new ArrayList<>();
//                            list.add(nums[i]);
//                            list.add(nums[j]);
//                            list.add(nums[k]);
//                            res.add(list);
//                        }
//                    }
//                }
//            }

            return res;
        }

        public List<List<Integer>> threeSum(int[] nums) {
            return threeSum2(nums);
        }
    }
}
